The present invention generally relates to content addressable memory and in particular, to a content addressable memory with programmable priority weighting and low cost match detection.
Content addressable memory (CAM) is useful in various applications such as address translation in network routers. FIG. 1 illustrates, as an example, a block diagram of a first prior art CAM arrangement including a CAM array 100 and a priority encoder 106. The CAM array 100 in this example has 2Nxe2x88x921 CAM cells, such as CAM cells 101xcx9c105. Each CAM cell includes a comparator and a register.
An input data word is provided to each CAM cell, and the CAM cell""s comparator compares the input data word against the entry in its register. If they match, a match indication, such as a binary xe2x80x9c1xe2x80x9d, is placed on the CAM cell""s output line, such as output line M0 of CAM cell 101. On the other hand, if they do not match, a no-match indication, such as a binary xe2x80x9c0xe2x80x9d, is placed on the output line.
The priority encoder 106 receives the match and no-match indications from the CAM array 100, and provides an N-bit binary output and a xe2x80x9cmatch detectxe2x80x9d output. If only one match indication is received, the N-bit binary output indicates an address location of the CAM cell register containing the matching entry. If multiple match indications are received, the priority encoder 106 first determines a winning match by selecting, for example, the match indication that is provided on a CAM cell output line corresponding to a highest physical position connection. The N-bit binary output then indicates the address location of a CAM cell register containing the winning matching entry.
The xe2x80x9cmatch detectxe2x80x9d output of the priority encoder 106 indicates whether or not the CAM array 100 has detected a match (i.e., whether at least one match indication has been received from the CAM array 100). If no match has been detected, then the N-bit binary output should be ignored. The xe2x80x9cmatch detectxe2x80x9d output may be generated at the output of OR logic by coupling all output lines M0xcx9cM2Nxe2x88x921 (wherein the symbol xe2x80x9cxcx9cxe2x80x9d indicates the sequence of output lines from M0 to M2Nxe2x88x921) of the CAM array 100 to inputs of the OR logic.
There are at least two perceived problems with the first prior art CAM arrangement. One problem is the fixed nature of its priority encoder 106 when determining a winning match among multiple match indications from the CAM array 100. In particular, it is advantageous in some applications to provide a capability to change the order of priority among the output lines of the CAM array 100. Otherwise, each time an entry is added or deleted from the CAM array 100, all of the entries would have to be rearranged again in proper priority order in the CAM array 100. Another problem is that generation of the xe2x80x9cmatch detectxe2x80x9d output may be circuit intensive when the number of match output lines is large. For example, a CAM array with 64K match output lines may require OR logic with 64K inputs to generate the xe2x80x9cmatch detectxe2x80x9d output.
FIG. 2 illustrates, as an example, a block diagram of a second prior art CAM arrangement including a CAM array 100, a weight array 200 and an encoder 206. This approach provides some level of flexibility in prioritizing match indications provided by the CAM array 100 on its output lines M0xcx9cM2Nxe2x88x921. The CAM array 100 is identical in construction and operation as that described in reference to FIG. 1, therefore, it is given the same reference number and its description is not repeated here.
The weight array 200 determines a winner among match indications received from the CAM array 100 according to their respectively assigned weights, such as 201xcx9c205, that are stored in the weight array 200. The winner is indicated, for example, by a binary xe2x80x9c1xe2x80x9d placed on one of the output lines W0xcx9cW2Nxe2x88x921 of the weight array 200, while non-winners are indicated by binary xe2x80x9c0""sxe2x80x9d placed on all other of the output lines W0xcx9cW2Nxe2x88x921.
The encoder 206 receives the winning and non-winning match information from the weight array 200, and provides an N-bit binary output and a xe2x80x9cmatch detectxe2x80x9d output. As in the first prior art CAM arrangement, the N-bit binary output indicates an address location of the CAM cell register containing the winning matching entry, and the xe2x80x9cmatch detectxe2x80x9d output indicates whether or not the CAM array 100 has detected a match. If no match has been detected, then the N-bit binary output should be ignored. The xe2x80x9cmatch detectxe2x80x9d output in this case may be generated at the output of OR logic by coupling all output lines W0xcx9cW2Nxe2x88x921 of the weight array 200 to inputs of the OR logic (i.e., if no winner is detected, then it is assumed that no match indications were received from the CAM array 100).
Although it provides some capability to change the order of priority among the output lines M0xcx9cM2Nxe2x88x921 of the CAM array 100, the second prior art CAM arrangement still generates the xe2x80x9cmatch detectxe2x80x9d output in much the same circuit intensive way as the first prior art CAM arrangement.
Accordingly, it is an object of the present invention to provide a content addressable memory with programmable priority weighting and low cost match detection.
Another object is to provide such a content addressable memory using minimal circuitry so as to minimize die size and therefore, cost of an integrated circuit device including such a content addressable memory.
These and additional objects are accomplished by the various aspects of the present invention, wherein briefly stated, one aspect is a content addressable memory comprising: a CAM array having a first plurality of addressable storage elements for storing a plurality of entries, comparison logic for comparing an input data word with individual of the plurality of entries, and a plurality of outputs providing match and no-match indications of the input data word with the plurality of entries; and a weight array coupled to the plurality of outputs of the CAM array for receiving the match and no-match indications, the weight array having a second plurality of addressable storage elements for storing weights respectively assigned to corresponding ones of the plurality of outputs of the CAM array and at least one storage element for storing a weight lower than the weights and assigned to a forced match indication, weight logic for determining a winner among the match indications and the forced match indication, and a plurality of outputs indicating the winner.
Another aspect is a method for determining whether a match has been detected by a content addressable memory, comprising: receiving match information from a content addressable memory for a plurality of lines assigned with weights; generating a forced match on a line assigned with a lowest weight; determining a winning match among the forced match and any matches indicated in the match information according to their respective weights; and determining whether a match has been detected by the content addressable memory from the success of the forced match being determined to be the winning match.
Another aspect is a weight array circuit employed to determine a winning match among indicated matches of a content addressable memory. A plurality of lines is individually coupled through a current limiting circuit to a high reference voltage at one end and open-ended at another end. A plurality of weight cells are organized in rows and columns, each column coupled to a corresponding one of the plurality of lines, and each row receiving a corresponding output of the content addressable memory to determine whether the corresponding output is a winning match. Individual of the plurality of weight cells include an addressable storage element for storing a weight value; a first NMOS transistor having a drain coupled to the corresponding one of the plurality of lines, and a gate coupled to the corresponding output of the content addressable memory if in a first column of the plurality of weight cells or an output of a prior weight cell in a same row if in any other column of the plurality of weight cells; a second NMOS transistor having a drain coupled to the first NMOS transistor source, a gate coupled to the output of the addressable storage element, and source coupled to a low reference voltage; a first NAND logic having a first input coupled to the first NMOS transistor gate, and second input coupled to the corresponding one of the plurality of lines; a second NAND logic having a first input coupled to the first NAND logic first input, and second input coupled to the output of the addressable storage element; and a third NAND logic having a first input coupled to the first NAND logic output, second input coupled to the second NAND logic output, and output providing an output indicating whether the corresponding output of the content addressable memory is a winning match if in a last column of the plurality of weight cells or an input to a next weight cell in the same row if in any other column of the plurality of weight cells.
Yet another aspect is a weight array circuit employed to determine a winning match among indicated matches of a content addressable memory. A plurality of lines is individually coupled through a current limiting circuit to a high reference voltage at one end and open-ended at another end. A plurality of weight cells are organized in rows and columns, each column is coupled to a corresponding one of the plurality of lines, and each row receives a corresponding output of a content addressable memory to determine whether the corresponding output is a winning match. Individual of the plurality of weight cells include: an addressable storage element for storing a weight value; a first NMOS transistor having a drain coupled to the corresponding one of the plurality of lines, and gate coupled to the corresponding output of the content addressable memory if in a first column of the plurality of weight cells or an output of a prior weight cell in a same row if in any other column of the plurality of weight cells; a first NAND logic having a first input coupled to the first NMOS transistor gate, and second input coupled to the corresponding one of the plurality of lines; first and second PMOS transistors, wherein the first and the second PMOS transistor sources are coupled to the high reference voltage, the first PMOS transistor gate is coupled to the first NMOS transistor gate, and the second PMOS transistor gate is coupled to the output of the addressable storage element; second and third NMOS transistors, wherein the second NMOS transistor drain is coupled to the first PMOS transistor drain and the second PMOS transistor drain, the second NMOS transistor gate is coupled to the first PMOS transistor gate, the third NMOS transistor drain is coupled to the first NMOS transistor source and the second NMOS transistor source, the third NMOS transistor gate is coupled to the output of the addressable storage element, and the third NMOS transistor source is coupled to a low reference voltage; and a third NAND logic having a first input coupled to the first NAND logic output, second input coupled to the drain of the second NMOS transistor, and output providing an output indicating whether the corresponding output of the content addressable memory is a winning match if in a last column of the plurality of weight cells or an input to a next weight cell in the same row if in any other column of the plurality of weight cells.
Additional objects, features and advantages of the various aspects of the present invention will become apparent from the following description of its preferred embodiment, which description should be taken in conjunction with the accompanying drawings.